package com.hanxiaozhang.search;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈斐波那契查找算法〉
 * <p>
 * 文章有时间好好看一下：
 * https://www.cnblogs.com/sha-Pao-Zi/p/16315064.html
 * <p>
 * 斐波那契查找算法是一种提升算法，它利用了斐波那契数列的特点对表进行分割，从而提高了查找效率。
 * 该算法的时间复杂度为O(log n)，比折半查找的平均性能更好，但最坏情况下的性能却比折半查找差。
 * 斐波那契查找的优点在于分割时只需加减运算，而二分法需要除2。
 * 斐波那契查找算法的实现方法有两种：递归和非递归。递归算法的时间复杂度为O(2^n)，而非递归算法的时间复杂度可以降到O(n)。
 * 因此，使用非递归算法实现斐波那契查找算法可以更快地计算斐波那契数列的前n项，并将结果保存在一个数组中。
 *
 * @author hanxinghua
 * @create 2023/12/20
 * @since 1.0.0
 */
public class FibonacciSearch {

    public static void main(String[] args) {
        // 目标数据组
        int[] arr = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};
        // 需要查找的数据
        int search = 39;
        // 返回索引位置
        int position = fibonacciSearch(arr, search);
        System.out.println("The index of the element " + search + " is: " + position);
    }

    /**
     * 斐波那契查找
     * <p>
     * 整体思路：
     * 1. 在斐波那契数列找一个等于或第一个大于查找表中元素个数的数 fibArray[k]
     * - Tips：此时斐波那契数列是存放在数组中的，所以会用fibArray[]表示, 一定要注意跟F()的不同, 比如: fibArray[6] =13 = fibArray(7)
     * 2. 将原查找表的长度扩展为fibArray[k]-1 ，如果要补充元素，则重复补充原查找表最后一个元素，直到原查找表个数中满足fibArray[k]-1
     * 3. 扩展完成后进行斐波那契分割，即 fibArray[k]-1个元素分割为前半部分fibArray[k-1]-1个元素，后半部分fibArray[k-2]-1个元素，
     * mid= low + fibArray[[k-1]-1。通过不断比较mid, 递归分割区间, 找到符合要求的那个数。
     *
     * @param arr
     * @param search
     * @return
     */
    public static int fibonacciSearch(int[] arr, int search) {

        // 查找左边界、右边界、比较值位置
        int left = 0, right = arr.length - 1, mid = 0;
        // 记录待查找序列长度应该为哪一个斐波那契数
        int k = 0;
        // 生成斐波那契数列的个数
        int maxsize = 20;

        // 生成斐波那契数列
        int[] fibArray = fibonacci(maxsize);

        // 判断待查找序列长度应该为哪一个斐波那契数
        while (right > fibArray[k] - 1) {
            k++;
        }

        // 填充待排序列, 长度为fibArray[k]-1
        // 把老数组复制到长度为fibArray[k]的新数组中，超出老数组长度的用0填充
        int[] temp = Arrays.copyOf(arr, fibArray[k]);

        // 填充temp数组中为0的部分，使用arr[right]补充
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];
        }

        // 开始查找
        while (left <= right) {
            // 求比较值位置
            mid = left + fibArray[k - 1] - 1;

            // 不断比较不同区间内 findVal 与 temp[mid]的关系
            if (search < temp[mid]) {
                right = mid - 1;
                k--;
            } else if (search > temp[mid]) {
                left = mid + 1;
                k -= 2;
            } else {
                if (mid <= right) {
                    return mid;
                } else {
                    return right;
                }
            }
        }

        return -1;
    }

    /**
     * 生成斐波那契数
     *
     * @param n
     * @return
     */
    public static int[] fibonacci(int n) {

        int[] fibArray = new int[n];

        if (n >= 1) {
            fibArray[0] = 0;
        }

        if (n >= 2) {
            fibArray[1] = 1;
        }

        for (int i = 2; i < n; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
        }

        return fibArray;
    }

}
